home *** CD-ROM | disk | FTP | other *** search
/ World of Education / World of Education.iso / world_s / sp12src.zip / EDITDIST.ASM < prev    next >
Assembly Source File  |  1989-03-20  |  6KB  |  186 lines
  1.          IDEAL
  2.          MODEL TPASCAL
  3.  
  4. STRUC    workarea ; allocated on stack
  5. saveds   DW    ?  ; save area for register DS
  6. xlen     DW    ?  ; length of translated x string
  7. d        DW    ?  ; pointer to beginning of d array on stack
  8. x        DW    ?  ; pointer to beginning of x array on stack
  9. yi       DW    ?  ; current y letter (translated)
  10. dy       DW    ?  ; insert distance for current y letter
  11. ENDS
  12.  
  13.          CODESEG
  14.  
  15.          ;     a b c d e f g h i j k l m n o p q r s t u v w x y z
  16. dist     db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1;
  17.          db  1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; a
  18.          db  1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; b
  19.          db  1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; c
  20.          db  1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; d
  21.          db  1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; e
  22.          db  1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; f
  23.          db  1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; g
  24.          db  1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; h
  25.          db  1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; i
  26.          db  1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; j
  27.          db  1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; k
  28.          db  1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1; l
  29.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1; m
  30.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1; n
  31.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1; o
  32.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1; p
  33.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1; q
  34.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1; r
  35.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1; s
  36.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1; t
  37.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1; u
  38.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1; v
  39.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1; w
  40.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1; x
  41.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1; y
  42.          db  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0; z
  43.  
  44. PUBLIC   EditDistance
  45. PROC     EditDistance FAR xadr:DWORD,yadr:DWORD
  46. LOCAL    work:workarea=worklen
  47.          Mov   [work.saveds],DS
  48.  
  49. ; move and translate string x to work area on stack
  50.  
  51.          Lds   SI,[xadr]
  52.          Mov   DX,SP         ;save SP for computation below
  53.          Dec   DX
  54.          Mov   DI,DX
  55.          Cld
  56.          LodsB
  57.          Or    AL,AL
  58.          Jz    xnull
  59.          Xor   AH,AH
  60.          Mov   CX,AX
  61.          Sub   SP,AX         ;temporarily make room for all of x
  62.          Add   SI,AX
  63.          Dec   SI
  64.          Mov   AX,SS
  65.          Mov   ES,AX
  66.          Std                 ;examine x string backwards
  67.  
  68. xloop:   LodsB
  69.          Or    AL,20h        ;only alphabetic characters need apply
  70.          Cmp   AL,'a'
  71.          Jl    loopx
  72.          Cmp   AL,'z'
  73.          Jg    loopx
  74.          Sub   AL,60h        ;normalize to 1..26
  75.          StosB
  76. loopx:   Loop  xloop
  77.  
  78. xnull:   Mov   AX,DX         ;compute length of valid x
  79.          Sub   AX,DI
  80.          Mov   [work.xlen],AX
  81.          Inc   DI
  82.          Mov   [work.x],DI
  83.          Inc   AX            ;d is 2*Succ(Length(x)) long
  84.          Shl   AX,1
  85.          Sub   DI,AX
  86.          Mov   [work.d],DI
  87.          Mov   SP,DI
  88.          Dec   SP
  89.  
  90. ; initialize d array (to first row of conceptual 2d array, dd[i,j])
  91.  
  92.          Mov   BX,SS
  93.          Mov   ES,BX         ;DI still has [work.d]
  94.          Xor   AX,AX
  95.          Mov   DX,AX
  96.          Cld
  97.          StosW               ;dd[0,0] := 0
  98.          Mov   CX,[work.xlen]
  99.          Or    CX,CX
  100.          Jz    stepd
  101.          Mov   DS,BX
  102.          Mov   SI,[Work.x]
  103.          Mov   BX,AX
  104. iloop:   LodsB               ;for j := 1 to xlen do
  105.          Mov   BL,AL
  106.          Mov   AL,[dist+BX]
  107.          Xor   AH,AH
  108.          Add   AX,DX
  109.          StosW               ;dd[0,j] := dd[0,j-1] + dist[0,x[j]];
  110.          Mov   DX,AX         ;at end of loop, DX = dd[0,xlen]
  111.          Loop  iloop
  112.  
  113. ; step d array down xy plane (d is a row of conceptual array dd[i,j])
  114.  
  115. stepd:   Lds   SI,[yadr]
  116.          LodsB
  117.          Or    AL,AL
  118.          Jz    done
  119.          Xor   AH,AH
  120.          Mov   CX,AX         ;for i := 1 to Length(y) do begin
  121.          Mov   AX,SS
  122.          Mov   ES,AX
  123.  
  124. nexty:   LodsB
  125.          Or    AL,20h        ;alpha only
  126.          Cmp   AL,'a'
  127.          Jl    loopy
  128.          Cmp   AL,'z'
  129.          Jg    loopy
  130.          Sub   AL,60h        ;normalize to 1..26,
  131.          Mov   BL,27
  132.          Mul   BL            ;then multiply by 27
  133.  
  134.          Push  DS            ; save regs and set up for inner loop
  135.          Push  SI
  136.          Push  CX
  137.          Mov   BX,SS
  138.          Mov   DS,BX
  139.          Mov   DI,[work.d]
  140.  
  141.          Mov   [work.yi],AX  ;yi := y[i];
  142.          Mov   BX,AX
  143.          Xor   AH,AH
  144.          Mov   AL,[dist+BX]
  145.          Mov   [work.dy],AX  ;dy := dist[y[i],0];
  146.          Add   AX,[Word ES:DI]   ;AX := dd[i-1,0] + dy;
  147.  
  148.          Mov   CX,[work.xlen]    ;for j := 1 to xlen do begin
  149.          Or    CX,CX
  150.          Jz    xdone
  151.          Mov   SI,[work.x]
  152.  
  153. nextx:   Mov   DX,[ES:DI]    ;DX := dd[i-1,j-1]
  154.          StosW               ;dd[i,j-1] := AX;
  155.          LodsB
  156.          Xor   AH,AH
  157.          Mov   BX,AX
  158.          Mov   AL,[dist+BX]
  159.          Add   AX,[ES:DI-2]  ;AX := dd[i,j-1] + dist[0,x[j]]
  160.          Add   BX,[work.yi]
  161.          Mov   BL,[dist+BX]
  162.          Xor   BH,BH
  163.          Add   DX,BX         ;DX := dd[i-1,j-1] + dist[y[i],x[j]]
  164.          Mov   BX,[ES:DI]
  165.          Add   BX,[work.dy]  ;BX := dd[i-1,j] + dist[y[i],0];
  166.          Cmp   AX,BX         ;AX := Min(AX,BX,DX)
  167.          Jle   skip1
  168.          Mov   AX,BX
  169. skip1:   Cmp   AX,DX
  170.          Jle   skip2
  171.          Mov   AX,DX
  172. skip2:   Loop  nextx
  173.  
  174. xdone:   StosW
  175.          Pop   CX
  176.          Pop   SI
  177.          Pop   DS
  178.          Mov   DX,AX
  179. loopy:   Loop  nexty
  180.  
  181. done:    Mov   DS,[work.saveds]
  182.          Mov   AX,DX
  183.          Ret                 ;function result is in AX
  184. ENDP
  185. END
  186.